from typing import List


class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        def check(avg):
            min_left_sum = left_sum = 0
            right_sum = sum(nums[i] - avg for i in range(k))
            for i in range(k, len(nums)):
                if right_sum >= min_left_sum:
                    return True
                left_sum += nums[i - k] - avg
                right_sum += nums[i] - avg
                min_left_sum = min(min_left_sum, left_sum)
            return right_sum >= min_left_sum

        left, right = -pow(10, 4), pow(10, 4)
        while left + pow(10, -6) < right:
            mid = (left + right) / 2
            if check(mid):
                left = mid
            else:
                right = mid
        return left


if __name__ == "__main__":
    print(Solution().findMaxAverage([1, 12, -5, -6, 50, 3], k=4))  # 12.75
